#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=60,MAXM=4e3+10;
int n,m,a[MAXM],b[MAXM],c[MAXM],C[MAXM],f[MAXN][MAXN][MAXM],g[MAXN][MAXN][MAXM],h[MAXN][MAXM],pos[MAXN][MAXN][MAXM],ans[MAXM];
void dfs(int l,int r,int k)
{
	if(l>r)return;
	int t=pos[l][r][k],mid=g[l][r][t];
	ans[mid]=C[t];
	dfs(l,mid-1,t);
	dfs(mid+1,r,t);
	return;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;++i)a[i]=read(),b[i]=read(),C[i]=c[i]=read();
	sort(C+1,C+1+m);
	for(int i=1;i<=m;++i)c[i]=lower_bound(C+1,C+1+m,c[i])-C;
	for(int len=1;len<=n;++len)
		for(int i=1;i+len-1<=n;++i)
		{
			int j=i+len-1;
			memset(h,0,sizeof(h));
			for(int k=1;k<=m;++k)
				if(i<=a[k]&&b[k]<=j)
					for(int l=a[k];l<=b[k];++l)
						++h[l][c[k]];
			for(int k=i;k<=j;++k)
				for(int l=m-1;l;--l)
					h[k][l]+=h[k][l+1];
			for(int k=m;k;--k)
			{
				int _max=0;
				for(int l=i;l<=j;++l)
				{
					int tmp=f[i][l-1][k]+f[l+1][j][k]+C[k]*h[l][k];
					if(tmp>=_max)_max=tmp,g[i][j][k]=l;
				}
				if(_max>=f[i][j][k+1])f[i][j][k]=_max,pos[i][j][k]=k;
				else f[i][j][k]=f[i][j][k+1],pos[i][j][k]=pos[i][j][k+1];
			}
		}
	dfs(1,n,1);
	printf("%d\n",f[1][n][1]);
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);
	puts("");
	return 0;
}
